<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>基于线性表的图书信息管理系统的设计与实现</title>
    <style>
        body {
            font-family: 宋体, SimSun, serif;
            font-size: 12pt;
            line-height: 1.5;
            margin: 40px;
            color: #000;
        }

        h1 {
            font-size: 14pt;
            font-weight: bold;
            text-align: left;
            margin-top: 24pt;
            margin-bottom: 12pt;
        }

        h2 {
            font-size: 12pt;
            font-weight: bold;
            text-align: left;
            margin-top: 12pt;
            margin-bottom: 6pt;
        }

        h3 {
            font-size: 12pt;
            font-weight: normal;
            text-indent: 2em;
            margin-top: 6pt;
            margin-bottom: 6pt;
        }

        p {
            text-indent: 2em;
            margin-bottom: 12pt;
        }

        .code-block {
            background-color: #f5f5f5;
            border: 1px solid #ddd;
            padding: 10px;
            font-family: 'Courier New', monospace;
            font-size: 10pt;
            line-height: 1.2;
            margin: 12pt 0;
        }

        table {
            border-collapse: collapse;
            width: 100%;
            margin: 12pt 0;
        }

        table,
        th,
        td {
            border: 1px solid #000;
        }

        th,
        td {
            padding: 8px;
            text-align: left;
        }

        th {
            background-color: #f0f0f0;
            font-weight: bold;
        }

        .mermaid {
            text-align: center;
            margin: 20px 0;
        }
    </style>
    <script src="https://cdn.jsdelivr.net/npm/mermaid@10/dist/mermaid.min.js"></script>
    <script>mermaid.initialize({ startOnLoad: true });</script>
</head>

<body>

    <h1>1 实验内容描述</h1>

    <p>本次实验要求我设计并实现一个基于线性表的图书信息管理系统。在着手开发的过程中，我首先对核心的数据结构进行了选型，最终决定采用双向链表来实现。我选择双向链表，主要是考虑到图书信息的增删操作会比较频繁，而双向链表在这方面比顺序表和单向链表都更有优势。整个系统需要实现的功能也比较全面，从最基础的创建和显示图书信息，到根据ISBN或书名进行查找、插入、删除、修改，再到对所有图书按价格进行排序，以及统计和文件导入导出，最后通过一个主菜单将这些功能整合起来，提供一个统一的操作界面。
    </p>

    <h1>2 算法实现所采用的存储结构的C语言描述</h1>

    <p>在选择存储结构时，我主要考虑了图书信息动态变化的特点。相比于需要预先分配固定空间的顺序表，链表显然更具弹性。而在单向链表和双向链表之间，我最终选择了带头结点的双向链表。虽然这会稍微增加一些内存开销，因为它需要一个额外的`prior`指针，但我认为这点牺牲是值得的，因为它极大地简化了删除和修改操作的逻辑，无需再为了找前驱节点而从头遍历。头结点的设计也让链表的插入和删除操作在处理边界条件时（比如在头部插入或删除）变得更加统一和简洁。为了方便管理，我还定义了几个全局变量：`length`用于实时记录图书数量，避免了每次都得遍历链表来统计；`head_1`、`head_2`和`head_3`则用来存储输出时的表头信息，确保了界面显示和文件导出格式的一致性。
    </p>

    <div class="code-block">
        struct Book {
        string id; // ISBN
        string name; // 书名
        double price; // 定价
        };

        typedef struct DuLNode {
        Book data; // 数据域
        struct DuLNode *prior; // 直接前驱
        struct DuLNode *next; // 直接后继
        } DuLNode, *DuLinkList;
    </div>

    <p>双向链表的结构示意图如下所示，每个结点包含数据域和两个指针域，形成了双向的链接关系：</p>

    <div class="mermaid">
        graph TB
        A["头结点<br />prior: NULL<br />next: →"] --> B["结点1<br />Book: 程序设计基础<br />prior: ←<br />next: →"]
        B --> C["结点2<br />Book: 单片机技术及应用<br />prior: ←<br />next: →"]
        C --> D["结点3<br />Book: 编译原理<br />prior: ←<br />next: →"]
        D --> E["...<br />更多结点"]
        E --> F["结点n<br />Book: Eclipse基础与应用<br />prior: ←<br />next: NULL"]

        B --> A
        C --> B
        D --> C
        F --> E

        style A fill:#f9f9f9
        style B fill:#e1f5fe
        style C fill:#e1f5fe
        style D fill:#e1f5fe
        style F fill:#e1f5fe
    </div>

    <h1>3 各算法步骤和算法描述</h1>

    <p>整个图书管理系统的数据流向和算法执行过程可以用以下流程图来描述，展现了用户操作与数据处理的完整流程：</p>

    <div class="mermaid">
        flowchart TD
        A["用户输入"] --> B{选择操作类型}
        B -->|1| C["文件读取"]
        B -->|2| D["键盘输入"]
        B -->|3| E["查找操作"]
        B -->|4| F["插入操作"]
        B -->|5| G["删除操作"]
        B -->|6| H["修改操作"]
        B -->|7| I["排序操作"]

        C --> C1["打开book.txt"]
        C1 --> C2["逐行读取数据"]
        C2 --> C3["创建新结点"]
        C3 --> C4["链表尾插"]
        C4 --> C5["更新length计数"]

        E --> E1{查找方式}
        E1 -->|ISBN| E2["精确匹配查找"]
        E1 -->|书名| E3["模糊匹配查找"]
        E2 --> E4["遍历链表比较"]
        E3 --> E4
        E4 --> E5["返回结果"]

        F --> F1["输入图书信息"]
        F1 --> F2["检查ISBN重复"]
        F2 --> F3["创建新结点"]
        F3 --> F4["尾插到链表"]
        F4 --> F5["更新length计数"]

        G --> G1["输入ISBN"]
        G1 --> G2["查找目标结点"]
        G2 --> G3["调整指针关系"]
        G3 --> G4["释放结点内存"]
        G4 --> G5["更新length计数"]

        I --> I1["冒泡排序"]
        I1 --> I2["比较相邻结点价格"]
        I2 --> I3["交换数据域"]
        I3 --> I4["继续下一轮比较"]
        I4 --> I5["排序完成"]

        style A fill:#f9f9f9
        style B fill:#fff3e0
        style C fill:#e8f5e8
        style E fill:#e3f2fd
        style F fill:#fce4ec
        style G fill:#ffebee
        style I fill:#f3e5f5
    </div>

    <h2>3.1 链表初始化与创建算法</h2>

    <p>系统启动后的第一步是初始化一个空的双向链表，这一步通过`InitDuList_L`函数完成，它会分配头结点并将其指针域设为空，为后续所有操作打下基础。真正的核心在于`CreateDuList_L`函数，它负责从`book.txt`文件中读取数据来创建链表。在实现这个功能时，我碰到的第一个难题就是如何处理书名中可能存在的空格。如果用普通的`cin`，一遇到空格读取就中断了，导致书名不完整。经过一番尝试，我发现`getline`函数配合`ws`操纵符是最好的解决方案，`ws`能巧妙地跳过前面的空白符，而`getline`则可以完整地读取一行直到遇到指定的分隔符（在这里是制表符`\t`）。同时，为了程序的健壮性，我还通过`file.peek()`来检测文件是否结束，避免读取到文件末尾的空行导致程序出错。
    </p>

    <div class="code-block">
        file >> p->data.id;
        getline(file >> ws, p->data.name, '\t');
        file >> p->data.price;
    </div>

    <h2>3.2 查找算法</h2>

    <p>查找功能是系统的核心，我设计了两种方式：按ISBN精确查找和按书名模糊查找。ISBN是唯一的，所以它的查找逻辑很简单，就是从头到尾遍历链表，逐个比较`id`字段，找到就返回节点指针。对于书名的模糊查找，我利用了C++
        string类的`find`方法，这个方法非常好用，用户只需要输入书名的一部分，就能匹配到所有包含该关键词的图书，极大地提升了用户体验。为了让结果更友好，我没有只返回第一个匹配项，而是遍历整个链表，把所有匹配的图书都列出来。在开发过程中我也考虑到，虽然目前是大小写敏感的，但未来可以很方便地通过将输入和目标字符串都转为小写来升级为大小写不敏感的搜索。
    </p>

    <h2>3.3 插入和删除算法</h2>

    <p>对于插入新图书的功能，我采用了尾插法，即将新书信息总是添加到链表的末尾。实现这个功能时，一个关键的步骤是必须先检查新书的ISBN是否已经存在，以保证数据的唯一性，这一步我直接复用了`SearchByISBN`函数。确认ISBN不重复后，就创建一个新节点，然后遍历链表找到当前的最后一个节点，将新节点链接上去。双向链表的`prior`指针在这里就派上了用场，让新旧节点间的双向链接建立得非常直接。当然，每次成功插入后，都不能忘记将全局计数器`length`加一。删除操作比插入要更小心一些，因为它涉及到指针的断开和重新链接。双向链表的优势在删除时体现得淋漓尽致，找到要删除的节点`p`后，只需要将`p`的前一个节点的`next`指针指向`p`的后一个节点，同时将`p`的后一个节点的`prior`指针指向`p`的前一个节点，就完成了链表的"修复"。整个过程不需要像单向链表那样为了找前驱节点而头疼。为了防止用户误操作，我还特意设计了一个确认环节：在真正执行删除前，先把要删除的图书信息打印出来，让用户确认，输入'y'后才执行删除并释放内存，否则就取消操作。
    </p>

    <h2>3.4 排序算法</h2>

    <p>排序功能我选择了实现起来比较直观的冒泡排序。虽然它的时间复杂度在最坏情况下是O(n²)，不算最优，但考虑到我们这个学生项目的数据量通常不会特别大，它的简洁易懂就成了最大的优点。为了避免复杂的指针操作带来的风险，我选择只交换节点内的`Book`数据，而不是交换整个节点的位置。我还给排序加了一个小小的优化：如果在某一次的内层循环中，一次交换都没有发生，那就说明整个序列已经有序了，可以直接跳出循环，提前结束排序。排序完成后，程序会自动调用显示函数，让用户能马上看到按价格从低到高排序后的结果。冒泡排序还是一个稳定排序，这意味着价格相同的书在排序后它们的相对位置不会改变，这也是一个不错的附带特性。
    </p>

    <h2>3.5 输入验证与异常处理算法</h2>

    <p>为了让程序更加"皮实"，我在很多地方都加入了输入验证和异常处理机制。比如，我写了一个`clearInputBuffer`函数专门用来清理输入流中多余的字符，这在用户输入了非法数据（比如要求输入数字却输入了字母）后非常关键，可以防止程序陷入死循环。一个典型的应用场景就是价格输入，我不仅验证了输入的是不是数字，还确保了它必须是一个正数。如果用户输入有误，程序会给出清晰的提示，并让用户重新输入，而不是粗暴地崩溃或者接受一个错误的数据。
    </p>

    <h1>4 程序测试过程展示</h1>

    <p>为了全面检验系统的功能和稳定性，我设计了一系列测试用例，涵盖了从正常功能到异常处理的方方面面。测试过程主要围绕`book.txt`提供的16条初始数据展开。首先，我测试了最基本的数据导入和显示功能。程序启动后选择从文件导入，系统能够成功读取`book.txt`中的全部16条记录，并且在显示时，无论是包含空格的书名还是带有特殊符号（如'C#'）的书名，都能被正确解析和展示，表格格式对齐，中文也无乱码。同时，我也测试了当`book.txt`不存在时的场景，程序能够给出友好的错误提示而不是崩溃。接着，我重点测试了查找功能。对于ISBN精确查找，我输入'9787302225065'，系统能准确无误地返回《数据结构（C语言版）》的完整信息。更有挑战性的是书名模糊查找，当我输入关键词"程序"时，系统正确地列出了所有书名包含这两个字的5本书，这证明了模糊匹配逻辑的正确性。对于查找不存在的ISBN或书名，系统也都能给出"未找到"的提示，整个流程符合预期。
    </p>

    <p>增删改功能的测试同样关键。我先尝试插入一本新书《Python编程实战》，ISBN为'9787302300000'，系统成功将其添加至列表末尾，总数也从16变为17。紧接着，我故意使用相同的ISBN再次插入，系统提示"ISBN已存在"并拒绝了操作，验证了数据唯一性约束的有效性。随后，我删除了刚才添加的新书，在确认提示后，该书被成功移除，总数恢复为16。对于修改功能，我将《计算机操作系统》的价格从17.00元改为20.00元，系统在修改成功后立刻显示了更新后的信息，数据准确无误。最后，我测试了排序功能，执行按价格排序后，列表确实按照价格从低到高重新排列，最便宜的图书和最贵的图书分别位于列表的两端，结果完全正确。除了这些核心功能，我还着重对各种异常情况和边缘场景进行了测试，以检验系统的健壮性。例如，在任何需要输入价格的地方，我都尝试输入负数、零、甚至字母，系统都能够识别为非法输入并要求用户重新输入。在空列表的状态下执行删除、修改、排序等操作，程序也能够正常处理而不会崩溃。在对程序进行反复的增删操作后，通过任务管理器观察内存占用，没有发现明显的内存泄漏，说明内存释放逻辑基本正确。虽然测试数据量不大，我还是简单地将数据文件扩充到百条级别，系统的各项操作响应速度依然很快，验证了当前设计对于中小规模数据是完全胜任的。
    </p>

    <table>
        <tr>
            <th>ISBN</th>
            <th>书名</th>
            <th>定价</th>
        </tr>
        <tr>
            <td>9787302257646</td>
            <td>程序设计基础</td>
            <td>25.00</td>
        </tr>
        <tr>
            <td>9787302219972</td>
            <td>单片机技术及应用</td>
            <td>32.00</td>
        </tr>
        <tr>
            <td>9787302203513</td>
            <td>编译原理</td>
            <td>46.00</td>
        </tr>
        <tr>
            <td>9787811234923</td>
            <td>汇编语言程序设计教程</td>
            <td>21.00</td>
        </tr>
        <tr>
            <td>9787512100831</td>
            <td>计算机操作系统</td>
            <td>17.00</td>
        </tr>
        <tr>
            <td>9787302265436</td>
            <td>计算机导论实验指导</td>
            <td>18.00</td>
        </tr>
        <tr>
            <td>9787302180630</td>
            <td>实用数据结构</td>
            <td>29.00</td>
        </tr>
        <tr>
            <td>9787302225065</td>
            <td>数据结构（C语言版）</td>
            <td>38.00</td>
        </tr>
    </table>

    <h1>5 存在的问题与思考</h1>

    <p>在完成整个系统的开发和测试后，我也冷静地思考了其中存在的不足和可以改进的地方。最明显的是性能问题，当前所有查找操作都是基于线性遍历，时间复杂度为O(n)，当数据量巨大时，性能瓶颈会非常突出。特别是对于ISBN这种唯一标识，如果能改用哈希表（在C++中可以用`std::unordered_map`）来存储，那么查找效率将能提升到近乎O(1)的水平。其次是数据持久化机制比较简陋，所有修改都只存在于内存中，必须手动导出才能保存，一旦程序异常退出，所有未保存的工作都会丢失。一个更完善的系统应该具备自动保存或者退出时提示保存的功能。在用户体验上，纯文本的命令行界面虽然能完成任务，但远不如图形界面直观友好，未来可以考虑使用Qt等工具进行升级，或者至少对文本界面进行美化，比如加入分页显示功能。从代码健壮性角度看，内存管理虽然注意了`delete`和`new`的配对，但C++中更现代和安全的做法是使用智能指针（如`std::unique_ptr`）来自动管理资源，避免潜在的内存泄漏风险。此外，数据验证还可以做得更严格，比如对ISBN的格式进行校验，而不仅仅是检查是否重复。最后，从系统架构来说，目前的功能比较单一，若要扩展成支持用户借阅、库存管理等功能的真正图书管理系统，就需要对数据结构和模块划分进行更深入的设计，并考虑多用户同时操作时的并发控制问题，这些都是未来可以深入研究的方向。
    </p>

    <h1>6 实验总结</h1>

    <p>通过这次完整的课程设计，我收获颇丰。这不仅仅是对数据结构课堂知识的一次检验，更是一次宝贵的、从零到一的软件开发全过程实践。我深刻体会到理论与实践的结合是多么重要，课堂上讲的双向链表在删除操作时的优势，只有在自己亲手实现并调试通过后，才有了真正切身的理解。在整个过程中，我锻炼了解决实际问题的能力，比如如何处理带空格的字符串输入、如何设计友好的用户交互、如何进行全面的功能测试等等。这些看似微小的细节，恰恰是决定一个软件产品质量的关键。我学会了从系统设计的角度去思考，不仅要实现功能，还要考虑其健壮性、易用性和未来的扩展性。编写代码不再是孤立地实现某个算法，而是要将各个功能模块有机地组织起来，形成一个协调工作的整体。同时，系统性的测试思维也在此过程中建立起来，我认识到编写代码和编写测试用例是同等重要的，只有经过严格测试的程序才是可靠的。总而言之，这次实验极大地提升了我的编程实践能力和工程思维，为我未来的学习和工作奠定了坚实的基础。
    </p>

</body>

</html>